package com.leetcode;

import javafx.util.Pair;

import java.util.LinkedList;
import java.util.logging.Level;

public class 接雨水 {
    public static void main(String[] args) {
        int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        System.out.println(trap(height));
    }

    public static int trap(int[] heights) {
        int maxRain = 0;
        LinkedList<Rain> linkedList = new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            Rain right = new Rain(i, heights[i]);

            while (!linkedList.isEmpty() && linkedList.peek().height < right.height) {
                Rain pop = linkedList.pop();
                Rain left = linkedList.peek();
                if (left != null) {
                    int width = right.index - left.index - 1;
                    int height = Math.min(left.height, right.height) - pop.height;
                    maxRain += width * height;
                }

            }
            linkedList.push(right);
        }
        return maxRain;
    }

    static class Rain {

        int index;
        int height;


        public Rain(int index, int height) {
            this.height = height;
            this.index = index;
        }

        @Override
        public String toString() {
            return String.valueOf(height);
        }
    }

}
